package com.demo.java.alg;

/**
 * 题目描述：
 *
 * 构造长度为N的数组arr，此数组需要满足： 对于任意 i < k < j ，arr[i] + arr[j] != 2 * arr[k] 。
 *
 * 奇数组          成立
 * 偶数组          成立
 * 奇数组 + 偶数组  成立
 */
public class LeftAddRightLess2Mid extends TestBase {

    public static int[] arr2(int n) {
        if (n <= 1) {
            return new int[]{1};
        }
        int halfSize = (n + 1) >> 1;// 二分计算
        int[] base = arr2(halfSize);

        int[] res = new int[n];
        int i = 0;
        // 计算奇数
        for (; i < base.length; i++) {
            res[i] = base[i] * 2 - 1;
        }
        // 计算偶数
        for (int j = 0; i < n; ++i, ++j) {
            res[i] = base[j] * 2;
        }
        return res;
    }

    /** 检验函数，暴力做法，判断arr是不是达标的。 */
    public static boolean isValid(int[] arr) {   // test()函数时间主要花在这里 O(N^3)
        int size = arr.length;
        for (int i = 0; i < size - 2; ++i) {
            for (int k = i + 1; k < size - 1; ++k) {
                for (int j = k + 1; j < size; ++j) {
                    if (arr[i] + arr[j] == 2 * arr[k]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        printArr(arr2(1));
        printArr(arr2(2));
        printArr(arr2(3));
        printArr(arr2(4));
        printArr(arr2(5));
        printArr(arr2(6));
        printArr(arr2(7));
        printArr(arr2(8));
        printArr(arr2(9));
        printArr(arr2(10));

        System.out.println(isValid(arr2(1)));
        System.out.println(isValid(arr2(2)));
        System.out.println(isValid(arr2(3)));
        System.out.println(isValid(arr2(4)));
        System.out.println(isValid(arr2(5)));
        System.out.println(isValid(arr2(6)));
        System.out.println(isValid(arr2(7)));
        System.out.println(isValid(arr2(8)));
        System.out.println(isValid(arr2(9)));
        System.out.println(isValid(arr2(10)));
    }
}
